<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from lidoref.tnf on 19 December 2010 -->

<TITLE>LIDO - Reference Manual - Computed Subtrees</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>LIDO - Reference Manual</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="lidoref_9.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="lidoref_11.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="lidoref_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<H1><A NAME="SEC18" HREF="lidoref_toc.html#SEC18">Computed Subtrees</A></H1>
<P>
In general the tree represents the abstract structure of the input text and is
built by scanning and parsing the input. That initial tree may be augmented by
subtrees which result from certain computations. This feature can be used for
translation into target trees which also contain computations that are
executed in the usual way.
<A NAME="IDX208"></A>
<P>
The tree construction functions generated by LIGA are used to build such
subtrees. They are inserted into the initial tree at certain positions
specified in productions.
<P>
<H4>Syntax</H4>
<PRE>
    Symbols ::= '$' SymbName
<A NAME="IDX209"></A>
</PRE>
<P>
<H4>Examples</H4>
<PRE>
    RULE: Block ::= '{' Decl Stmts '}' $ Target COMPUTE
      Target.GENTREE =
           MkTBlock (COORDREF, Dels.tcode, Stmt.tcode);
    END;
    RULE TBlock: Target ::= TSeq TSeq COMPUTE ... END;
</PRE>
<P>
Trees may be the result of computations using LIGA's tree construction functions as
described below (see  <A HREF="lidoref_10.html#SEC19">Tree Construction Functions</A>).
<P>
Tree values may be propagated between computations using attributes of the
predefined type <CODE>NODEPTR</CODE> (see  <A HREF="lidoref_12.html#SEC21">Predefined Entities</A>).
<A NAME="IDX211"></A>
<A NAME="IDX210"></A>
<P>
Tree values are inserted into the tree in contexts where the right-hand
side of the production specifies <DFN>insertion points</DFN> 
of the form <CODE>$ X</CODE> where <CODE>X</CODE> is a nonterminal name.
<A NAME="IDX212"></A>
<P>
The insertion is specified by a computation of the attribute <CODE>X.GENTREE</CODE>
where <CODE>X</CODE> is the insertion point symbol and <CODE>GENTREE</CODE> is 
a predefined attribute name for inherited attributes of insertion 
symbols (see  <A HREF="lidoref_12.html#SEC21">Predefined Entities</A>). The computation
must yield a value of type <CODE>NODEPTR</CODE> that is a legal tree 
with respect to
the tree grammar for <CODE>X</CODE>: LIGA guarantees that the computations in the
inserted tree are not executed before the tree is inserted.
<A NAME="IDX214"></A>
<A NAME="IDX213"></A>
<P>
The tree grammar productions for computed trees may be disjoint from or may
overlap with the productions for the initial tree.
<A NAME="IDX216"></A>
<A NAME="IDX215"></A>
<P>
Computed trees may again have insertion points in their productions.
<P>
<H4>Restrictions</H4>
<P>
There must be exactly one insertion computation for each insertion point of a
rule context.
<P>
There may not be an insertion computation for a symbol that is not an insertion
point.
<P>
Inserted trees must be legal with respect to the tree grammar. This property is
checked at runtime of the evaluator.
<P>
No computation that establishes a precondition for a tree insertion may
depended on a computation within the inserted tree.
<P>
Contexts that may belong to subtrees which are built by
computations may not have
computations that are marked <CODE>BOTTOMUP</CODE> or contribute to
<CODE>BOTTOMUP</CODE> computations (see  <A HREF="lidoref_5.html#SEC6">Computations</A>).
<A NAME="IDX218"></A>
<A NAME="IDX217"></A>
<P>
<H2><A NAME="SEC19" HREF="lidoref_toc.html#SEC19">Tree Construction Functions</A></H2>
<P>
LIGA generates a set of tree construction functions, one for each
rule context. They may be used in computations to build trees which are then 
inserted at insertion points. Their names and signatures reflect the 
rule name and the right-hand side of the production.
<A NAME="IDX220"></A>
<A NAME="IDX219"></A>
<P>
For a rule
<PRE>
    RULE pBlock: Block::= '{' Decls Stmts '}' END
</PRE>
<P>
there is a function
<PRE>
    NODEPTR MkpBlock (POSITION *c, NODEPTR d1, NODEPTR d2)
</PRE>
<P>
The function name is the rule name prefixed by <CODE>Mk</CODE>. Hence, it is
recommended not to omit the rule name when its construction function
is to be used.
<P>
LIGA's tree construction functions are ready to be used in attribute 
computations. If they are to be applied in user-supplied C-code an include 
directive
<P>
<PRE>
   #include "treecon.h"
</PRE>
<P>
has to be used to make the function definitions available.
<P>
The first parameter of every function is a pointer to a 
source coordinate. 
That argument may be obtained from the coordinate of the context where
the function is called. It is used for error reporting, see 
 <A HREF="lidoref_12.html#SEC21">Predefined Entities</A>.
<P>
The following parameters correspond to the sequence of non-literal
symbols of the right-hand side of the production.
For each nonterminal in the production there is a parameter of type
<CODE>NODEPTR</CODE>. Its argument must be a pointer to the root node of a 
suitable subtree, built by node construction functions.
<A NAME="IDX221"></A>
For each insertion point in the production there is a parameter of
type <CODE>NODEPTR</CODE>. Its argument should be <CODE>NULLNODEPTR</CODE>, since that
subtree is inserted later by a computation.
<A NAME="IDX222"></A>
For each named terminal in the production there is a parameter
of the type of the terminal. Its argument is the value that is to
be passed to terminal uses in computations.
<A NAME="IDX224"></A>
<A NAME="IDX223"></A>
<P>
Functions for chain productions, the right-hand side of which consists
of exactly one nonterminal, need not be called explicitly. The nodes
for those contexts are inserted implicitly when the upper context 
is built.
<A NAME="IDX226"></A>
<A NAME="IDX225"></A>
<P>
<CODE>LISTOF</CODE> productions have a specific set of tree 
construction functions:
For a rule like
<P>
<PRE>
    RULE pDecls: Decls LISTOF Var | Proc | END;
</PRE>
the functions
<PRE>
    NODEPTR MkpDecls (POSITION *c, NODEPTR l)
    NODEPTR Mk2pDecls (POSITION *c, NODEPTR ll, NODEPTR lr)
</PRE>
<P>
are provided, where <CODE>Mk2pDecls</CODE> constructs internal list context
nodes and <CODE>MkpDecls</CODE> builds the root context of the list.
<P>
The arguments for each of the parameters <CODE>l</CODE>, <CODE>ll</CODE>, and 
<CODE>lr</CODE>
can be <CODE>NULLNODEPTR</CODE> representing an empty list, a pointer to a list
element node, a node that can be made a list element subtree by implicit 
insertion of chain contexts, or the result of a <CODE>Mk2</CODE>-function call
representing a sublist.
<P>
The <CODE>Mk2</CODE>-functions concatenate two intermediate list 
representations into one retaining the order of their elements.
<P>
<CODE>Mk0</CODE>-macros are generated. They take only the <CODE>POSITION</CODE>
but no tree as argument, and return  <CODE>NULLNODEPTR</CODE> representing an 
empty list. These macros usually need not be used.
<P>
The <CODE>LISTOF</CODE> subtree must be finally built by a call of the 
root context function. 
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="lidoref_9.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="lidoref_11.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="lidoref_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
